Method: miniMax(int, double, double)

1: package de.fhdw.gaming.ipspiel22.searchtree.algorithm;
2:
3: import java.util.LinkedHashMap;
4: import java.util.List;
5: import java.util.Map;
6: import java.util.Optional;
7: import de.fhdw.gaming.core.domain.GameException;
8: import de.fhdw.gaming.core.domain.Move;
9: import de.fhdw.gaming.core.domain.Player;
10: import de.fhdw.gaming.core.domain.State;
11: import de.fhdw.gaming.ipspiel22.searchtree.domain.MinMaxGame;
12:
13: /**
14: * MinMax algorithm implementation.
15: *
16: * @param <P> The type of player.
17: * @param <S> The type of state.
18: * @param <M> The type of move.
19: * @param <G> The type of object implementing the {@link MinMaxGame} interface.
20: */
21: public final class MinMaxAlgorithm<P extends Player<P>, S extends State<P, S>, M extends Move<P, S>,
22: G extends MinMaxGame<P, S, M>> {
23: /**
24: * Variable for the class with the necessary functions.
25: */
26: private final G game;
27:
28: /**
29: * Constructs an object of this class.
30: *
31: * @param game The interface to the underlying game.
32: */
33: public MinMaxAlgorithm(final G game) {
34: this.game = game;
35: }
36:
37: /**
38: * Returns the best move for the current player.
39: *
40: * @param depth The search depth.
41: */
42: public Optional<M> getBestMove(final int depth) throws GameException {
43: if (this.game.isGameOver()) {
44: return Optional.empty();
45: }
46: final Map<M, Double> scores = new LinkedHashMap<>();
47: for (final M move : this.game.getPossibleMoves()) {
48: this.game.commitMove(move);
49: scores.put(move, -this.miniMax(depth, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
50: this.game.rollbackMove(move);
51: }
52: return scores.entrySet().stream().max((e1, e2) -> e1.getValue().compareTo(e2.getValue()))
53: .map(Map.Entry::getKey);
54: }
55:
56: /**
57: * MinMax algorithm which calculates the best next move.
58: *
59: * @param depth the depth of searching (moves in the future).
60: * @param alpha alpha value for alpha-beta pruning (on first call: -inf).
61: * @param beta beta value for alpha-beta pruning (on first call: +inf).
62: * @return the value for the next move.
63: */
64: public double miniMax(final int depth, final double alpha, final double beta) throws GameException {
65:• if (depth == 0 || this.game.isGameOver()) {
66: return this.game.evaluateStateful();
67: }
68: double maxWert = alpha;
69: final List<M> moves = this.game.getPossibleMoves();
70:• for (final M move : moves) {
71: this.game.commitMove(move);
72: final double wert = -this.miniMax(depth - 1, -beta, -maxWert);
73: this.game.rollbackMove(move);
74:• if (wert > maxWert) {
75: maxWert = wert;
76:• if (maxWert >= beta) {
77: break;
78: }
79: }
80: }
81: return maxWert;
82: }
83: }